翻訳と辞書 Words near each other ・ Difference engine ・ Difference feminism ・ Difference gel electrophoresis ・ Difference hierarchy ・ Difference in differences ・ Difference in the depth of modulation ・ Difference list ・ Difference of Gaussians ・ Difference of Opinion ・ Difference of two squares ・ Difference polynomials ・ Difference quotient ・ Difference set ・ Difference theory ・ Difference United ・ Difference-map algorithm ・ Differences (journal) ・ Differences (song) ・ Differences between Sunni, Shia and Ibadi Islam ・ Different ・ Different (Kate Ryan album) ・ Different (Robbie Williams song) ・ Different (Thomas Anders album) ・ Different Cars and Trains ・ Different Class ・ Different Colors ・ Different Damage ・ Different Directions ・ Different Directions (Champion album) ・ Different Directions (John Denver album) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Difference-map algorithm ： ウィキペディア英語版 Difference-map algorithm The difference-map algorithm is a search algorithm for general constraint satisfaction problems. It is a meta-algorithm in the sense that it is built from more basic algorithms that perform projections onto constraint sets. From a mathematical perspective, the difference-map algorithm is a dynamical system based on a mapping of Euclidean space. Solutions are encoded as fixed points of the mapping. Although originally conceived as a general method for solving the phase problem, the difference-map algorithm has been used for the boolean satisfiability problem, protein structure prediction, Ramsey numbers, diophantine equations, and ''Sudoku'',〔V. Elser, I. Rankenburg, and P. Thibault, "Searching with iterated maps". ''Proceedings of the National Academy of Sciences'' USA. (2007). 104:418-423. http://www.pnas.org/cgi/content/short/104/2/418〕 as well as sphere- and disk-packing problems.〔S. Gravel, V. Elser, "Divide and concur: A general approach to constraint satisfaction". ''Physical Review E''. (2008). 78:036706. http://link.aps.org/doi/10.1103/PhysRevE.78.036706〕 Since these applications include NP-complete problems, the scope of the difference map is that of an incomplete algorithm. Whereas incomplete algorithms can efficiently verify solutions (once a candidate is found), they cannot prove that a solution does not exist. The difference-map algorithm is a generalization of two iterative methods: Fienup's Hybrid input output (HIO) algorithm for phase retrieval 〔J.R. Fienup, "Phase retrieval algorithms: a comparison". ''Applied Optics''. (1982). 21:2758-2769.〕 and the Douglas-Rachford algorithm〔H.H. Bauschke, P.L. Combettes, and D.R. Luke, "Phase retrieval, error reduction algorithm, and Fienup variants: a view from convex optimization". ''Journal of the Optical Society of America A''. (2002). 19:1334-1345.〕 for convex optimization. Iterative methods, in general, have a long history in phase retrieval and convex optimization. The use of this style of algorithm for hard, non-convex problems is a more recent development. ==Algorithm== The problem to be solved must first be formulated as a set intersection problem in Euclidean space: find an $x$ in the intersection of sets $A$ and $B$. Another prerequisite is an implementation of the projections $P\_A$ and $P\_B$ that, given an arbitrary input point $x$, return a point in the constraint set $A$ or $B$ that is nearest to $x$. One iteration of the algorithm is given by the mapping: :$$ \begin x \mapsto D(x) &= x + \beta \left(P_A \left( f_B(x)\right) - P_B \left( f_A(x)\right)\right ), \\ f_A(x) &= P_A(x) - \frac\left( P_A(x) - x\right), \\ f_B(x) &= P_B(x) + \frac\left( P_B(x) - x\right) \end The real parameter $\backslash beta$ should not be equal to 0 but can have either sign; optimal values depend on the application and are determined through experimentation. As a first guess, the choice $\backslash beta\; =\; 1$ (or $\backslash beta\; =\; -1$) is recommended because it reduces the number of projection computations per iteration: :$D(x)\; =\; x\; +\; P\_A\backslash left(\; 2P\_B(x)\; -\; x\backslash right)-P\_B(x)$ A point $x$ is a fixed point of the map $x\; \backslash mapsto\; D(x)$ precisely when $P\_A\backslash left(f\_B(x)\backslash right)\; =\; P\_B\backslash left(f\_A(x)\backslash right)$. Since the left-hand side is an element of $A$ and the RHS is an element of $B$, the equality implies that we have found a common element to the two constraint sets. Note that the fixed point $x$ itself need not belong to either $A$ or $B$. The set of fixed points will typically have much higher dimension than the set of solutions. The progress of the algorithm can be monitored by inspecting the norm of the difference of the two projections: :$\backslash Delta\; =\; \backslash left|\; P\_A\; \backslash left(\; f\_B(x)\backslash right)\; -\; P\_B\; \backslash left(\; f\_A(x)\backslash right)\backslash right|$. When this vanishes, a point common to both constraint sets has been found and the algorithm can be terminated. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Difference-map algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.